#include "jpsMe.h"
#include <cmath>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <unordered_set>

static const int16_t weighl = 100;
static const int16_t weighh = 141;
static const vector<Pos> directs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1}};
unordered_map<Pos, int8_t, PosHash> dirIdxMap = {{{0, 1}, 0}, {{0, -1}, 1}, {{1, 0}, 2}, {{-1, 0}, 3}, {{1, 1}, 4}, {{-1, 1}, 5}, {{1, -1}, 6}, {{-1, -1}, 7}};

bool operator==(const Pos &lhs, const Pos &rhs)
{
    return lhs.x_ == rhs.x_ && lhs.y_ == rhs.y_;
}

bool JpsMe::posEqual(Pos a, Pos b)
{
    if (a.x_ == b.x_ && a.y_ == b.y_)
        return true;
    return false;
}

int JpsMe::evaluateCost(Pos s, Pos e)
{
    double dis = pow((s.x_ - e.x_), 2) + pow((s.y_ - e.y_), 2);
    dis = sqrt(dis);
    return dis * 100;
}

bool JpsMe::sideCheck(int x, int y)
{
    if (x < 0 || x >= mapLength() || y < 0 || y >= mapWidth())
        return false;
    return true;
}

bool JpsMe::walkAble(int x, int y)
{
    if (x < 0 || x >= mapLength() || y < 0 || y >= mapWidth())
        return false;
    if (this->mapInfo_[x][y])
        return false;
    return true;
}

void JpsMe::initMapByLengthAndWidth(int mapLength, int mapWidth)
{
    mapInfo_ = vector<vector<int8_t>>(mapLength, vector<int8_t>(mapWidth, 0));
}

void JpsMe::initMapByFile(const string &fileName)
{
    mapInfo_ = {};
    ifstream f(fileName);
    int n;
    string line;
    while (getline(f, line))
    {
        vector<int8_t> vl;
        istringstream iss(line);
        while (iss >> n)
            vl.push_back(n);
        mapInfo_.push_back(vl);
    }
    f.close();
}

void JpsMe::setMap(Pos leftBottom, Pos rightTop, int8_t t)
{
    if (!sideCheck(leftBottom.x_, leftBottom.y_) || !sideCheck(rightTop.x_, rightTop.y_))
        return;
    if (leftBottom.x_ > rightTop.x_ || leftBottom.y_ > rightTop.y_)
        return;
    for (int i = leftBottom.x_; i <= rightTop.x_; ++i)
    {
        for (int j = leftBottom.y_; j <= rightTop.y_; ++j)
        {
            this->mapInfo_[i][j] = t;
        }
    }
}

void JpsMe::setMapAndUpdateJp(Pos leftBottom, Pos rightTop, int8_t t)
{
    if (!sideCheck(leftBottom.x_, leftBottom.y_) || !sideCheck(rightTop.x_, rightTop.y_))
        return;
    if (leftBottom.x_ > rightTop.x_ || leftBottom.y_ > rightTop.y_)
        return;
    for (int i = leftBottom.x_; i <= rightTop.x_; ++i)
    {
        for (int j = leftBottom.y_; j <= rightTop.y_; ++j)
        {
            this->mapInfo_[i][j] = t;
        }
    }
    Pos lb{leftBottom.x_ - 1, leftBottom.y_ - 1};
    if (lb.x_ < 0)
        lb.x_ += 1;
    if (lb.y_ < 0)
        lb.y_ += 1;
    Pos rt{rightTop.x_ + 1, rightTop.y_ + 1};
    if (rt.x_ >= mapLength())
        rt.x_ -= 1;
    if (rt.y_ >= mapWidth())
        rt.y_ -= 1;
    vector<int> xs;
    vector<int> ys;
    for (int i = lb.x_; i <= rt.x_; ++i)
    {
        xs.push_back(i);
    }
    for (int i = lb.y_; i <= rt.y_; ++i)
    {
        ys.push_back(i);
    }
    for (int i = lb.x_; i <= rt.x_; ++i)
    {
        for (int j = lb.y_; j <= rt.y_; ++j)
        {
            this->jpInfo_[i][j] = vector<int16_t>(4, 0);
        }
    }
    for (auto x : xs)
    {
        this->jp({x, 0}, {0, 1});
        this->jp({x, mapWidth() - 1}, {0, -1});
    }
    for (auto y : ys)
    {
        this->jp({0, y}, {1, 0});
        this->jp({mapLength() - 1, y}, {-1, 0});
    }
}

bool JpsMe::forceNeighbor(Pos p, Pos direct)
{
    bool b = false;

    int x1 = p.x_ + direct.y_;
    int y1 = p.y_ + direct.x_;
    int x11 = x1 + direct.x_;
    int y11 = y1 + direct.y_;
    if (this->sideCheck(x1, y1) && this->sideCheck(x11, y11))
    {
        if (!walkAble(x1, y1) && walkAble(x11, y11))
        {
            b = b || true;
        }
    }

    int x2 = p.x_ - direct.y_;
    int y2 = p.y_ - direct.x_;
    int x21 = x2 + direct.x_;
    int y21 = y2 + direct.y_;
    if (this->sideCheck(x2, y2) && this->sideCheck(x21, y21))
    {
        if (!walkAble(x2, y2) && walkAble(x21, y21))
        {
            b = b || true;
        }
    }
    return b;
}

bool JpsMe::jp(Pos t, Pos direct)
{
    Pos q = t;
    while (sideCheck(q.x_, q.y_) && !walkAble(q.x_, q.y_))
    {
        q.x_ += direct.x_;
        q.y_ += direct.y_;
    }
    if (!sideCheck(q.x_, q.y_))
        return false;

    Pos p = q;
    int i = 0;
    while (1)
    {
        if (!walkAble(p.x_, p.y_))
        {
            --i;
            for (int j = 0; j <= i; ++j)
            {
                Pos p2{q.x_ + direct.x_ * j, q.y_ + direct.y_ * j};
                auto &jp = this->jpInfo_[p2.x_][p2.y_];
                jp[dirIdxMap[{direct.x_, direct.y_}]] = 0;
                if (i - j > 0)
                    jp[dirIdxMap[{direct.x_, direct.y_}]] = i - j;
            }
            this->jp(p, direct);
            return false;
        }
        if (this->forceNeighbor(p, direct) && i)
        {
            for (int j = 0; j <= i; ++j)
            {
                Pos p2{q.x_ + direct.x_ * j, q.y_ + direct.y_ * j};
                auto &jp = this->jpInfo_[p2.x_][p2.y_];
                jp[dirIdxMap[{direct.x_, direct.y_}]] = 0;
                if (i - j > 0)
                    jp[dirIdxMap[{direct.x_, direct.y_}]] = i - j;
            }
            this->jp(p, direct);
            return true;
        }
        p.x_ += direct.x_;
        p.y_ += direct.y_;
        ++i;
    }
}
void JpsMe::initJpInfo()
{
    this->jpInfo_ = vector<vector<vector<int16_t>>>(mapLength(), vector<vector<int16_t>>(mapWidth(), vector<int16_t>(4, 0)));
    for (int i = 0; i < mapLength(); ++i)
    {
        this->jp({i, 0}, {0, 1});
        this->jp({i, mapWidth() - 1}, {0, -1});
    }
    for (int i = 0; i < mapWidth(); ++i)
    {
        this->jp({0, i}, {1, 0});
        this->jp({mapLength() - 1, i}, {-1, 0});
    }
}

bool JpsMe::findEnd(Pos p, Pos end, Pos direct)
{
    if (this->posEqual(p, end))
        return true;
    if (p.x_ != end.x_ && p.y_ != end.y_)
        return false;
    int dx = end.x_ - p.x_;
    int dy = end.y_ - p.y_;
    if (dx)
        dx = dx > 0 ? 1 : -1;
    if (dy)
        dy = dy > 0 ? 1 : -1;
    if (dx != direct.x_ || dy != direct.y_)
        return false;

    auto &jp = jpInfo_[p.x_][p.y_];
    int len = jp[dirIdxMap[{direct.x_, direct.y_}]];
    if (len <= 0)
        return false;
    Pos newP{p.x_ + dx * len, p.y_ + dy * len};
    if (p.x_ <= end.x_ && p.y_ <= end.y_ && end.x_ <= newP.x_ && end.y_ <= newP.y_)
        return true;
    if (p.x_ >= end.x_ && p.y_ >= end.y_ && end.x_ >= newP.x_ && end.y_ >= newP.y_)
        return true;
    return false;
}

bool JpsMe::addJpToOpenList(State p, Pos end, Pos direct, priority_queue<State> &openList, unordered_map<Pos, Pos, PosHash> &pres)
{
    State s = p;
    auto &jp = jpInfo_[p.x_][p.y_];
    int len = jp[dirIdxMap[{direct.x_, direct.y_}]];
    if (len <= 0)
        return false;
    p.x_ += direct.x_ * len;
    p.y_ += direct.y_ * len;
    p.cost_ += weighl * len;
    // if (!walkAble(p.x_ + direct.x_, p.y_ + direct.y_))
    //     return false;

    bool b = this->addForceNeighbor(p, end, direct, openList, pres);
    if (b)
    {
        if (pres.end() == pres.find({p.x_, p.y_}))
        {
            p.weigh_ = p.cost_ + this->evaluateCost({p.x_, p.y_}, end);
            p.directX_ = direct.x_;
            p.directY_ = direct.y_;
            openList.push(p);
            pres[{p.x_, p.y_}] = {s.x_, s.y_};
        }
    }
    return b;
}

bool JpsMe::addForceNeighbor(State start, Pos end, Pos direct, priority_queue<State> &openList, unordered_map<Pos, Pos, PosHash> &pres)
{
    bool b = false;

    int x1 = start.x_ + direct.y_;
    int y1 = start.y_ + direct.x_;
    int x11 = x1 + direct.x_;
    int y11 = y1 + direct.y_;
    if (this->sideCheck(x1, y1) && this->sideCheck(x11, y11))
    {
        if (!walkAble(x1, y1) && walkAble(x11, y11))
        {
            b = b || true;
            int cost = start.cost_ + weighh;
            int weigh = this->posEqual({x11, y11}, end) ? 0 : cost + this->evaluateCost({x11, y11}, end);
            State s{x11, y11, cost, weigh, direct.x_ + direct.y_, direct.y_ + direct.x_};
            if (pres.end() == pres.find({s.x_, s.y_}))
            {
                openList.push(s);
                pres[{s.x_, s.y_}] = {start.x_, start.y_};
            }
        }
    }

    int x2 = start.x_ - direct.y_;
    int y2 = start.y_ - direct.x_;
    int x21 = x2 + direct.x_;
    int y21 = y2 + direct.y_;
    if (this->sideCheck(x2, y2) && this->sideCheck(x21, y21))
    {
        if (!walkAble(x2, y2) && walkAble(x21, y21))
        {
            b = b || true;
            int cost = start.cost_ + weighh;
            int weigh = this->posEqual({x21, y21}, end) ? 0 : cost + this->evaluateCost({x21, y21}, end);
            State s{x21, y21, cost, weigh, direct.x_ - direct.y_, direct.y_ - direct.x_};
            if (pres.end() == pres.find({s.x_, s.y_}))
            {
                openList.push(s);
                pres[{s.x_, s.y_}] = {start.x_, start.y_};
            }
        }
    }
    return b;
}

bool JpsMe::jumpPoint(State start, Pos end, Pos direct, priority_queue<State> &openList, unordered_map<Pos, Pos, PosHash> &pres)
{
    start.directX_ = direct.x_;
    start.directY_ = direct.y_;
    State s = start;
    while (1)
    {
        if (!direct.x_ || !direct.y_)
        {
            if (!this->walkAble(s.x_, s.y_))
                return false;
            if (this->findEnd({s.x_, s.y_}, end, direct))
            {
                State t{end.x_, end.y_, 0, 0};
                if (pres.end() == pres.find(end))
                {
                    openList.push(t);
                    pres[end] = {start.x_, start.y_};
                }
                return true;
            }
            if (this->addJpToOpenList(s, end, direct, openList, pres))
                return true;
            return false;
        }
        else
        {
            bool b = false;
            b = this->addForceNeighbor(s, end, {direct.x_, 0}, openList, pres) || b;
            b = this->addForceNeighbor(s, end, {0, direct.y_}, openList, pres) || b;
            if (b)
            {
                if (!this->posEqual({s.x_, s.y_}, {start.x_, start.y_}) && pres.end() == pres.find({s.x_, s.y_}))
                {
                    pres[{s.x_, s.y_}] = {start.x_, start.y_};
                }
                int x = s.x_;
                int y = s.y_;
                int dx = direct.x_;
                int dy = direct.y_;
                bool b1 = this->sideCheck(x + dx, y) && !walkAble(x + dx, y);
                bool b2 = this->sideCheck(x, y + dy) && !walkAble(x, y + dy);
                bool b3 = this->sideCheck(x + dx, y + dy) && walkAble(x + dx, y + dy);
                if ((b1 || b2) && b3)
                    return true;
            }

            s.x_ += direct.x_;
            s.y_ += direct.y_;
            s.cost_ += weighh;
            if (!this->walkAble(s.x_, s.y_))
                return false;
            if (this->posEqual({s.x_, s.y_}, end))
            {
                s.weigh_ = 0;
                if (pres.end() == pres.find({s.x_, s.y_}))
                {
                    openList.push(s);
                    pres[{s.x_, s.y_}] = {start.x_, start.y_};
                    return true;
                }
            }
            bool r = false;
            r = this->jumpPoint(s, end, {direct.x_, 0}, openList, pres) || r;
            r = this->jumpPoint(s, end, {0, direct.y_}, openList, pres) || r;
            if (r)
            {
                if (pres.end() == pres.find({s.x_, s.y_}))
                {
                    pres[{s.x_, s.y_}] = {start.x_, start.y_};
                    s.x_ += direct.x_;
                    s.y_ += direct.y_;
                    s.cost_ += weighh;
                    s.weigh_ = this->posEqual({s.x_, s.y_}, end) ? 0 : s.cost_ + evaluateCost({s.x_, s.y_}, end);
                    if (walkAble(s.x_, s.y_) && pres.end() == pres.find({s.x_, s.y_}))
                    {
                        openList.push(s);
                        pres[{s.x_, s.y_}] = {start.x_, start.y_};
                    }
                    return true;
                }
            }
        }
    }
}
void JpsMe::search(Pos start, Pos end, vector<Pos> &result)
{
    if (!walkAble(start.x_, start.y_) || !walkAble(end.x_, end.y_))
        return;

    unordered_set<Pos, PosHash> closeList;
    priority_queue<State> openList;
    int weigh = this->evaluateCost(start, end);
    State stateS{start.x_, start.y_, 0, weigh, 0, 0};
    unordered_map<Pos, Pos, PosHash> pres;
    openList.push(stateS);

    while (!openList.empty())
    {
        State t = openList.top();
        openList.pop();
        if (closeList.end() != closeList.find({t.x_, t.y_}))
            continue;
        closeList.insert({t.x_, t.y_});
        if (t.x_ == end.x_ && t.y_ == end.y_)
        {
            result.push_back(end);
            Pos p(end.x_, end.y_);
            while (pres.end() != pres.find(p))
            {
                Pos pre = pres[p];
                p.x_ = pre.x_;
                p.y_ = pre.y_;
                result.push_back(p);
            }
            return;
        }

        int directX = t.directX_;
        int directY = t.directY_;
        vector<Pos> dps;
        if (!directX && !directY)
        {
            PosDirectComp p;
            p.start = start;
            p.end = end;
            dps = directs;
            sort(dps.begin(), dps.end(), p);
        }
        else if (directX && directY)
        {
            dps.push_back({directX, 0});
            dps.push_back({0, directY});
            dps.push_back({directX, directY});
        }
        else
        {
            dps.push_back({directX, directY});
        }
        for (int i = 0; i < dps.size(); ++i)
        {
            this->jumpPoint(t, end, dps[i], openList, pres);
        }
    }
}

//-------------------------js cpp binding-----------------------
Nan::Persistent<v8::Function> JpsMe::constructor;

NAN_MODULE_INIT(JpsMe::Init)
{
    v8::Local<v8::FunctionTemplate> tpl = Nan::New<v8::FunctionTemplate>(New);
    tpl->SetClassName(Nan::New("pathFinding").ToLocalChecked());
    tpl->InstanceTemplate()->SetInternalFieldCount(1);

    Nan::SetPrototypeMethod(tpl, "mapLength", MAPLENGTH);
    Nan::SetPrototypeMethod(tpl, "mapWidth", MAPWIDTH);
    Nan::SetPrototypeMethod(tpl, "initMapByLengthAndWidth", INITMAPBYLENGTHANDWIDTH);
    Nan::SetPrototypeMethod(tpl, "initMapByFile", INITMAPBYFILE);
    Nan::SetPrototypeMethod(tpl, "initJpInfo", INITJPINFO);
    Nan::SetPrototypeMethod(tpl, "setMap", SETMAP);
    Nan::SetPrototypeMethod(tpl, "setMapAndUpdateJp", SETMAPANDUPDATEJP);
    Nan::SetPrototypeMethod(tpl, "search", SEARCH);

    constructor.Reset(Nan::GetFunction(tpl).ToLocalChecked());
    Nan::Set(target, Nan::New("pathFinding").ToLocalChecked(), Nan::GetFunction(tpl).ToLocalChecked());
}
NAN_METHOD(JpsMe::New)
{
    if (info.IsConstructCall())
    {
        JpsMe *p = new JpsMe();
        p->Wrap(info.This());
        info.GetReturnValue().Set(info.This());
    }
    else
    {
        const int argc = 1;
        v8::Local<v8::Value> argv[argc] = {info[0]};
        v8::Local<v8::Function> cons = Nan::New(constructor);
        info.GetReturnValue().Set(Nan::NewInstance(cons, argc, argv).ToLocalChecked());
    }
}

NAN_METHOD(JpsMe::MAPLENGTH)
{
    JpsMe *p = Nan::ObjectWrap::Unwrap<JpsMe>(info.This());
    int mapLength = p->mapLength();
    info.GetReturnValue().Set(mapLength);
}
NAN_METHOD(JpsMe::MAPWIDTH)
{
    JpsMe *p = Nan::ObjectWrap::Unwrap<JpsMe>(info.This());
    int mapWidth = p->mapWidth();
    info.GetReturnValue().Set(mapWidth);
}
NAN_METHOD(JpsMe::INITMAPBYLENGTHANDWIDTH)
{
    JpsMe *p = Nan::ObjectWrap::Unwrap<JpsMe>(info.This());
    int mapLength = info[0]->Int32Value();
    int mapWidth = info[1]->Int32Value();
    p->initMapByLengthAndWidth(mapLength, mapWidth);
    info.GetReturnValue().Set(1);
}
NAN_METHOD(JpsMe::INITMAPBYFILE)
{
    JpsMe *p = Nan::ObjectWrap::Unwrap<JpsMe>(info.This());
    v8::String::Utf8Value fName(info[0]->ToString());
    std::string fileName = std::string(*fName);
    p->initMapByFile(fileName);
    info.GetReturnValue().Set(1);
}
NAN_METHOD(JpsMe::INITJPINFO)
{
    JpsMe *p = Nan::ObjectWrap::Unwrap<JpsMe>(info.This());
    p->initJpInfo();
    info.GetReturnValue().Set(1);
}
NAN_METHOD(JpsMe::SETMAP)
{
    JpsMe *p = Nan::ObjectWrap::Unwrap<JpsMe>(info.This());
    int lbx = info[0]->Int32Value();
    int lby = info[1]->Int32Value();
    int rtx = info[2]->Int32Value();
    int rty = info[3]->Int32Value();
    int blockType = info[4]->Int32Value();
    p->setMap({lbx, lby}, {rtx, rty}, blockType);
    info.GetReturnValue().Set(1);
}
NAN_METHOD(JpsMe::SETMAPANDUPDATEJP)
{
    JpsMe *p = Nan::ObjectWrap::Unwrap<JpsMe>(info.This());
    int lbx = info[0]->Int32Value();
    int lby = info[1]->Int32Value();
    int rtx = info[2]->Int32Value();
    int rty = info[3]->Int32Value();
    int blockType = info[4]->Int32Value();
    p->setMapAndUpdateJp({lbx, lby}, {rtx, rty}, blockType);
    info.GetReturnValue().Set(1);
}
NAN_METHOD(JpsMe::SEARCH)
{
    JpsMe *p = Nan::ObjectWrap::Unwrap<JpsMe>(info.This());
    int startX = info[0]->Int32Value();
    int startY = info[1]->Int32Value();
    int endX = info[2]->Int32Value();
    int endY = info[3]->Int32Value();
    vector<Pos> result;
    p->search({startX, startY}, {endX, endY}, result);
    v8::Local<v8::Array> arr = Nan::New<v8::Array>(result.size() * 2);
    int i = 0;
    for (int j = result.size() - 1; j >= 0; --j)
    {
        Nan::Set(arr, i++, Nan::New(result[j].x_));
        Nan::Set(arr, i++, Nan::New(result[j].y_));
    }
    info.GetReturnValue().Set(arr);
}